/**
 * 
 */
package leetCode;

import java.util.HashSet;

/**
 * @author zhongfang
 *
 */
public class SmallestRange {
    public static int[] smallestRange(int[][] nums) {
    	int k=nums.length;
        int[] indexs=new int[k];
        int[] minRange=new int[2];
        int endCount=0;
        HashSet<Integer> endIndexs=new HashSet<>();
        while (endCount!=k) {
        	int min=100001;
        	int max=-100001;
        	int minIndex = 0;
        	
        	int deadMin=100001;
        	int aliveMIn=100001;
			for (int i = 0; i < k; i++) {
				if(endIndexs.contains(i)&&nums[i][indexs[i]]<deadMin){
					deadMin=nums[i][indexs[i]];
				}else if (!endIndexs.contains(i)&&nums[i][indexs[i]]<aliveMIn) {
					aliveMIn=nums[i][indexs[i]];
					minIndex=i;
				}
				if(nums[i][indexs[i]]>max){
					max=nums[i][indexs[i]];
				}
			}
			min=Math.min(aliveMIn, deadMin);
			if((minRange[0]==0&&minRange[1]==0)||(max-min<minRange[1]-minRange[0])||(max-min==minRange[1]-minRange[0])&&(min<minRange[0])){
				minRange[0]=min;
				minRange[1]=max;
			}
			
			if(indexs[minIndex]==nums[minIndex].length-1){
				if(endIndexs.add(minIndex)){
					endCount++;
				}
			}else {
				indexs[minIndex]++;//最小值向前走一步
			}
		}
        return minRange;
    }
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[][] nums={{4,10,15,24,26}, {0,9,12,20}, {5,18,22,30}};
		int[] range=smallestRange(nums);
		System.out.println(range[0]+" "+range[1]);
	}

}
